public class MySingleList implements IList {



    //创建一个链表
    static class ListNode{
        public int val;//每个节点的值
        public ListNode next;//next是一个引用，用于指向链表中的下一个节点的引用

        public ListNode(int val){
            this.val = val;
        }
    }

    //链表的属性 链表的头节点 用于标记链表的起始位置
    public ListNode head;

    //创建多个节点
    public void createList(){
            ListNode node1 = new ListNode(12);
            ListNode node2 = new ListNode(23);
            ListNode node3 = new ListNode(34);
            ListNode node4 = new ListNode(45);

            node1.next = node2;
            node2.next = node3;
            node3.next = node4;

            this.head = node1;
    }


    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
                node.next = head;
                this.head = node;
    }

    @Override
    public void addLast(int data) {
        ListNode  node = new ListNode(data);
        if(head == null){
            head = node;
        }else{
            ListNode cur = head;
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    @Override
    public void addIndex(int index, int data) throws IndexException {
        if(index < 0 || index > size()){
            throw new RuntimeException("Index 不合法： "+ index);
        }

        ListNode node = new ListNode(data);

        //头插
        if(index == 0){
            addFirst(data);
            return;
        }

        //尾插
        if(index == size()){
            addLast(data);
            return;
        }

        //合法位置插
        ListNode cur = searchPrevIndex(index);
        node.next = cur.next;
        cur.next = node;

    }

    //查找插入节点index的前一个节点的方法
    private ListNode searchPrevIndex(int index){
        ListNode cur = head;
        int count = 0;
        if(count != index - 1){
            cur = cur.next;
            count++;
        }
        return cur;
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                return  true;
            }
            cur = cur.next;
        }
        return  false;
    }

    @Override
    public void remove(int key) {
        //如果链表为空，即无元素需要删除
        if(head == null){
            return;
        }
        //如果头节点的值就是要删除的
        if(head.val == key){
            head = head.next;
            return;
        }

        //正常节点的删除
        ListNode mycur = findPreKey(key);//找到要删除的前一个节点
        ListNode del = mycur.next;
        if(mycur == null){
            return;//未找到要删除的元素
        }else{
            mycur.next = del.next;
        }
    }

    //①查找要删除的key的前一个节点的方法
        private ListNode findPreKey(int key) {
            ListNode cur = head;
        while(cur.next != null ){
            if (cur.next.val != key){
                cur = cur.next;
            }else{
                return  cur;
            }

        }
        return null;
    }



    @Override
    public void removeAllKey(int key) {
        //如果头为空，说明这个链表无元素，直接返回
        if(head == null){
            return;
        }

        ListNode prev = head;
        ListNode cur = prev.next;

        //特殊情况：头结点就是要删除的值的处理方式①
        while(head != null){
            if(head.val == key){
                head = head.next;
            }
        }

        //一般情况的删除
        while (cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }

//        //特殊情况：头结点就是要删除的值的处理方式②
//        if(head.val == key){
//            head = head.next;
//        }
    }

    @Override
    public int size() {
        int count = 0 ;
        ListNode cur = head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    @Override
    public void clear() {
        head = null;
    }

    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
    }

    public void display(ListNode newHead) {
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }



    public ListNode reverseList() {
        //如果头指针为空
        if(head == null){return head;}
        //如果只有一个头指针
        if(head.next == null){return head;}
        //如果有多个指针
        //step1:先保存头节点之后的节点
        ListNode cur = head.next;
        //step2:将头节点指向空，从而使其变成尾结点
        head.next = null;
        while(cur != null){
            //step3：头差法：
            //先记录第一个要头插节点cur之后的节点
            ListNode curNext = cur.next;
            //然后将cur这个 节点进行头插
            cur.next = head;
            //然后现在的头结点应该是cur
            head = cur;
            //新的cur应该是curNext
            cur = curNext;
            //重复上面头插步骤，直到cur = null 才结束头插
        }

        return head;
    }


    public int kthToLast(ListNode head, int k) {
        if (k < 0  ){
            return 0;
        }

        //细节处理：当头节点为空，即没有节点时
        if(head == null){
            return  0;
        }

        ListNode fast = head;
        ListNode slow = head;

        //计步变量
        int count = 0;

        while(count != k - 1){
            //为了不计算链表大小，
            //我们可以通过快慢指针之间位置永远差k - 1的关系
            //每次判断，fast指针是否在还未到k - 1位置之前
            //指向了空，指向空说明，超出链表大小，返回空；
            //相反，就是符合条件
            if(fast.next != null){
                fast = fast.next;
                count++;}else{
                return 0;
                //k比链表还大的优化代码，这就可以不用求链表长度
            }
        }

        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }


    public static ListNode partition(ListNode head, int x) {

        if(head == null){
            return null;
        }

        //定义一个cur 指向链表的头结点，用于遍历链表
        ListNode cur = head;

        ListNode bs = null;
        ListNode be = null;

        ListNode as = null;
        ListNode ae = null;

        //使用cur遍历所有节点
        while(cur != null){
            //1.先讨论节点的分类
            if(cur.val < x){
                //2.然后讨论节点是否为第一个头节点
                if(as == null){
                    as = cur;
                    ae = cur;
                }else{//>=x情况
                    //将后面节点插入到第一个节点后面，通过ae来操作
                    ae.next = cur ;
                    ae = ae.next;
                }
            }else {
                //讨论是否为b链表的头结点
                if(bs == null){
                    bs = cur;
                    be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }
            cur = cur.next;
        }

        if(as == null){
            return bs;
        }else{
            ae.next = bs;
            //讨论b是否为空
            if(bs  != null){
                be.next = null;
            }else{
                return as;
            }
            return as;
        }
    }

    // 获取头结点
    public ListNode getHead() {
        return this.head;
    }

    // 设置头结点（用于更新分区后的链表）
    public void setHead(ListNode newHead) {
        this.head = newHead;
    }

//    --------------------------------------------------
//    回文链表

    public boolean isPalindrome() {

        //特殊情况：head为空
        if(head == null){
            return true;
        }


        //1.先找中间节点
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        //2.翻转中间节点
        ListNode cur = slow.next;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //3.移动头结点和slow指针
        while(slow != head){
            //判断它们的值是否相等
            if(slow.val != head.val){
                return  false;
            }

            //偶数个节点的情况
            if(head.next == slow){
                return true;
            }

                slow = slow.next;
                head = head.next;

        }
        return true;
    }

}
